package test;

import java.lang.reflect.Array;

public class Demo_02 {
    //排序算法---------查找算法   练习
    public static void main(String[] args){
        int[] array ={8,5,3,9,6,4,8,65,33,52};
        maoPao(array);
        for(int i:array){//遍历
            System.out.print(i+" ");
        }



        //选择排序
        /*

        */


    }
    //冒泡排序（优化）---------------------------
    public static void maoPao(int[] array){

        /*for(int i=0;i<array.length;i++){
            for(int j=0;j<array.length-i-1;j++){
                if(array[j]>array[j+1]){
                    int k = array[j];
                    array[j] =array[j+1];
                    array[j+1] = k;
                }
            }*/
        //冒泡排序优化
        for(int i = 0;i<array.length;i++){
            boolean over=true;
            for(int j =0;j<array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    over = false;
                    int k = array[j];
                    array[j] =array[j+1];
                    array[j+1] = k;
                }
            }
            if(over){
                break;
            }
        }
    }
    //选择排序（优化）---------------------------
    public static void xuanZe(int[] array){
        for(int i=0;i<array.length;i++){
            int min=i;
            for(int j=i+1;j<array.length-1;j++){
                if(array[min]>array[j]){
                    min=j;
                }
            }
            if(min==i){
                continue;
            }
            int util =array[i];
            array[i]=array[min];
            array[min]=util;
        }
    }
    //插入排序----------------------------------
    public static void chaRu(int[] array){
        for(int i=1;i<array.length;i++) {
            int value = array[i];
            int indext = i - 1;
            while (indext >= 0 && value < array[indext]) {
                array[indext + 1] = array[indext];
                indext--;
            }
            array[indext + 1] = value;
        }

    }
    //希尔排序----------------------------------
    public static void xiEr(int[] array) {
        for(int i=array.length/2;i>0;i/=2){
            for(int j=i;j<array.length;j++){
                for(int k=j-i;k>=0;k-=i){
                    if(array[k+i]<array[k]){//jiaohuan
                        int util = array[k];
                        array[k]=array[k+i];
                        array[k+i]=util;
                    }
                }
            }
        }

    }
    //快速排序----------------------------------
    public static void kuaiSu(int[]array,int left,int right){
        int l=left;//左指针
        int r=right;//右指针
        int pivot =(l+r)/2;//中心轴下标
        int value = array[pivot];//中心轴值

        while(l<r){
            while(array[l]<value){//在中心轴左边找知道找到一个大于中心轴的数值 array【l】
                l++;
            }
            while(array[r]>value){//在中心轴右边找知道找到一个大于中心轴的数值 array【r】
                r--;
            }
            if(l>=r){//如果左边指针大于等于右边指针下标
                break;
            }
            //交换
            int util=array[l];
            array[l]=array[r];
            array[r]=util;

            if(array[l]==value){
                r--;
            }
            if(array[r]==value){
                l++;
            }
            /*for(int kkk:array){//为了方便调试理解
                System.out.print(kkk+" ");
            }
            System.out.println("-----------------"+l+r);*/

        }
        if(l==r){
            l++;
            r--;
        }
        if(left<r){//左递归
            kuaiSu(array,left,r);
        }
        if(right>l){//右递归
            kuaiSu(array,l,right);
        }

    }
    //快速排序（练习）---------------------------
    public static void kuaiSu2(int[]array,int left,int right){
        int l = left;//左指针
        int r = right;//右指针
        int z = (r+l)/2;
        int zhong = array[z];//中心轴--值
        while (l<r){
            while(array[l]<zhong){
                l++;
            }
            while(array[r]>zhong){
                r--;
            }
            //交换
            int value=array[l];
            array[l]=array[r];
            array[r]=value;

            if(array[l]==zhong){
                r--;
            }
            if (array[r]==zhong){
                l++;
            }
        }



    }

    //二分查找----------------------------------
    public static int erFen(int[]array,int value){
        int max=array.length-1;
        int min=0;
        while(true){
            int zhong =(max+min)/2;
            if(value>array[zhong]){
                min=zhong+1;
            }
            if(value<array[zhong]){
                max=zhong-1;
            }
            if (array[zhong]==value){
                return zhong;
            }
            if(min>max){
                return -1;
            }

        }
    }
    //二分查找（递归写法）---------------------------
    public static int erFen2(int[]array,int value,int max,int min){
        if(min>max||value<array[min]||value>array[max]){//核心代码
            return-1;
        }
        int zhong = (max+min)/2;
        if(value>array[zhong]){
            return erFen2(array,value,max,zhong+1);
        }
       else if(value<array[zhong]){
            return erFen2(array,value,zhong-1,min);
        }
        else if (value==array[zhong]){
            return zhong;
        }else {
            return -1;
        }
    }
    //插值查找（递归写法）
    public static int chaZhi(int[]array,int value,int max, int min){
        if(min>max||value<array[min]||value>array[max]){//核心代码
            return-1;
        }
        int zhong = min+(max-min)*(value-array[min])/(array[max]-array[min]);


        if(value>array[zhong]){
            return chaZhi(array,value,max,zhong+1);
        }
        else if(value<array[zhong]){
            return chaZhi(array,value,zhong-1,min);
        }
        else if (value==array[zhong]){
            return zhong;
        }else {
            return -1;
        }


    }
}
